package BinaryTree.后序;

import 其他.DataStructure.TreeNode;

/**
 * 本题 没画草图 干写的
 *
 * 尽量  ->  简化 思路 缩变量  ->  不易错
 */
public class 二叉树的最近公共祖先236 {
    TreeNode t1, t2; // pq唯一 （ val可同但pq不同
    int flag = 0;
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        t1 = p;
        t2 = q;
        back(root);
        return res;
    }
    private int back(TreeNode cur) {
        // flag=1 res已存好 -> 直接 瞎r
        if (flag == 1) {
            return 99;
        }
        if (cur == null) {
            return 0;
        }

        // 末1 正n
        int leftRes = back(cur.left);
        int rightRes = back(cur.right);

        //  h ( 简化 思路 缩变量
        int curRes = 0;
        if (cur == t1 || cur == t2) {
            curRes = 1;
        }
        int sum = curRes + leftRes + rightRes; // p q 永远不重 -> 因为：可以val同 但还是2个节点
        if (sum == 2) {
            flag = 1;
            res = cur;
            return 99;
        } else {
            return sum;
        }
    }
}
